package fda.sort;

import fda.base.Tuple;
import fda.schema.TableInfo;

/**
 * Class SortEngine for Sorting using Quick Sort Algorithm
 * 
 */
public class SortEngine {
	
	Tuple[] subList;
	int subListLength;
	private final TableInfo tableInfo;

	public SortEngine(TableInfo table){
		this.tableInfo = table;
	}
	
	/**
	 * @param mem sublist to order
	 * @return ordered sublist
	 */
	public Tuple[] sort(Tuple[] mem){	
		this.subList = mem;
        this.subListLength = mem.length;      
		quickSort(0, subListLength - 1);
		return subList;
	}

	/**
	 * @param low
	 * @param high
	 */
	private void quickSort(int low, int high) {
     int i = low, j = high;

      // Get the pivot element 
     long pivot = subList[low + (high-low)/2].getKeyValue();	
     
     // Divide into two lists
     while (i <= j) {
       // If the current Customer Id from the left list is smaller than the pivot
       //  then get the next line from the left list
       while (subList[i].getKeyValue() < pivot) {
         i++;
       }
       // If the current Customer Id from the right list is larger than the pivot
       //  then get the next line from the right list
       while (subList[j].getKeyValue() > pivot) {
         j--;
       }

       // exchange the values if any Customer Id from the left list is larger 
       // the the pivot or if any Customer Id from the right list is smaller 
       // than the pivot
       if (i <= j) {
         exchange(i, j);
         i++;
         j--;
       }
     }
     
 	// Recursion
     if (low < j)
       quickSort(low, j);
     if (i < high)
       quickSort(i, high);
     
	}
	
	/**
	 * @param i
	 * @param j
	 */
	private void exchange(int i, int j) {
	    String temp = subList[i].getLine();
	    subList[i] = subList[j];
	    subList[j] = new Tuple(temp, tableInfo);
	  }

}

